package base.template;

import java.util.ArrayList;
import java.util.List;


public class Fibonacci implements Generator<Integer> {
	private int count = 0;

	public Integer next() {
		return fib(count++);
	}

	public int fib(int n) {
		if (n < 2)
			return 1;
		return fib(n - 2) + fib(n - 1);
	}
	public int fib1(int n){
		int result=0;
		List<Integer> list=new ArrayList<Integer>();
		list.add(1);
		list.add(1);
		for(int i=2;i<n;i++){
			int len=list.size();
			result=list.get(len-1)+list.get(len-2);
			list.add(result);
		}
		result=list.get(list.size()-1);
		return result;
	}
	
	public int fib2(int n){
		int result=0;
		int first=1;
		int last=1;
		for(int i=2;i<n;i++){
			result=first+last;
			first=last;
			last=result;
		}
		result=last;
		return result;
	}

	public static void main(String[] args) {
		Fibonacci cci=new Fibonacci();
//		for(int i=0;i<18;i++){
//			System.out.print(cci.next()+" ");
//		}
//		System.out.println(cci.fib(50));
		int result=cci.fib2(50);
		System.out.println(result);
	}

}
